package cn.leetcode.array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个整数数组，判断是否存在重复元素。------>核心：去重。
 * <p>
 * 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 *
 * @author dunlingzi
 * @date 2021/11/7
 */
public class RepeatElement {

    public static void main(String[] args) {
        //例子：[1,1,1,3,3,4,3,2,4,2]；[1,2,3,1]
        int[] intArray = new int[]{1, 2, 3, 4};
        boolean result = Solution.containsDuplicate(intArray);
        System.out.println(result);
    }

    /**
     * 暴力破解,双重for循环，
     * 超出时间限制 O(n)=n的平方
     */
    static class Solution {
        public static boolean containsDuplicate(int[] nums) {
            boolean result = false;
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[i] == nums[j]) {
                        result = true;
                        break;
                    }
                }
                if (result) {
                    break;
                }
            }

            return result;
        }
    }

    /**
     * 关键在于Arrays.sort()排序算法,jdk自带的排序算法
     * 经过调优排序算法，性能能达到n*log(n)
     */
    static class Solution1 {
        public static boolean containsDuplicate(int[] nums) {
            boolean result = false;
            //排序
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] == nums[i + 1]) {
                    result = true;
                    break;
                }
            }

            return result;
        }
    }

    /**
     * 使用set集合存储不重复元素
     */
    static class Solution2 {
        public static boolean containsDuplicate(int[] nums) {
            boolean result = false;
            Set<Integer> numSets = new HashSet<>();
            int length = nums.length;
            for (int num : nums) {
                numSets.add(num);
            }
            if (numSets.size() < length) {
                result = true;
            }

            return result;
        }
    }

    /**
     * 借用jdk8的流去重方法
     */
    static class Solution3 {
        public static boolean containsDuplicate(int[] nums) {
            return Arrays.stream(nums).distinct().count() == nums.length;
        }
    }
}
